// 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
/*  输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
*/
//回溯法
var permute = function(nums) {
  const res = [];
  const path = [];
  const used = new Array(nums.length).fill(false); //标记每个元素是否已经被使用。

  function backtrack() {
    // 终止条件：路径长度等于数组长度
    if (path.length === nums.length) {
      res.push([...path]); // 拷贝当前路径
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // 已经用过的数字跳过

      path.push(nums[i]);
      used[i] = true;

      backtrack(); // 继续递归

      // 回溯：撤销选择
      path.pop();
      used[i] = false;
    }
  }

  backtrack();
  return res;
};
// 测试
console.log(permute([1,2,3]));

